#include "stdio.h"
#include "malloc.h"
/*
满二叉树
*/
#define MAXSIZE 100
typedef char SqBiTree[MAXSIZE];
SqBiTree bt;

/*二叉树-顺序存储，虚结点*/
/*二叉树，链式结构*/
typedef char DataType;
typedef struct node {
    DataType data;
    struct node *lchild, *rchild;
} BinTNode;
typedef BinTNode *BinTree;

/*三叉链表,方便二叉树找前趋*/
typedef struct trinode {
    DataType data;
    struct trinode *lchild, *parent, *rchild;
} BinTriTNode;
typedef BinTriTNode *BinTriTree;

/**
 * 按广义表表示二叉树，生成二叉树链的结构
 *
 * St[0] = p NULL
 * St[1] A结点
 * B结点 A的左子树
 * C结点 A的右子树
 * @param str
 * @return
 */
BinTNode * CreateTree(char *str) {
    BinTNode *St[100]; //用指针数组模拟栈。
    int top = -1; //栈顶标识
    BinTNode *p = NULL;
    BinTriTree b = NULL;
    int k; //标志位区分左右子树
    int j = 0; //循环标识位
    char ch = str[j];
    while (ch != '\0') {
        switch (ch) {
            case '(':
                top++;
                St[top] = p;
                k = 1;
                break;
            case ')':
                top--;
                break;
            case ',':
                k = 2;
                break;
            default:
                p = (BinTNode *) malloc(sizeof(BinTNode));
                p->data = ch;
                p->lchild = p->rchild = NULL;
                if (b == NULL) {
                    b = p;//建立结点
                } else {
                    switch (k) {
                        case 1:
                            St[top]->lchild = p;
                            break;
                        case 2:
                            St[top]->rchild = p;
                            break;
                        default:
                            break;
                    }
                }
                break;
        }
        j++;
        ch = str[j];
    }
    return b;
}

void printBtree2(BinTNode *bitNode) {
    printf("bitNode-Data:%c ", bitNode->data);
    printf("bitNode->lchild-data:%c", bitNode->lchild->data);
    printf("bitNode->rchild-data:%c", bitNode->rchild->data);
}

void preOrder(BinTNode *bitNode) {
    if (bitNode != NULL) {
        printf("%c", bitNode->data);
        preOrder(bitNode->lchild);
        preOrder(bitNode->rchild);
        return;
    }
}

void InOrder(BinTNode *binTNode) {
    if (binTNode != NULL) {
        InOrder(binTNode->lchild);
        printf("%c", binTNode->data);
        InOrder(binTNode->rchild);
    }
}

void postOrder(BinTNode *binTNode) {
    if (binTNode != NULL) {
        postOrder(binTNode->lchild);
        postOrder(binTNode->rchild);
        printf("%c", binTNode->data);
    }
}

#define stackSize 100
typedef BinTree DataType2;
typedef struct {
    DataType2 data[stackSize];
    int top;
} SeqStack;

/*置空栈*/
void InitStack(SeqStack *S) {
    S->top = -1;
}

/*判栈空*/
int StackEmpty(SeqStack *S) {
    return S->top == -1;
}

/*判栈满*/
int StackFull(SeqStack *S) {
    return S->top == stackSize - 1;
}

/*进栈*/
void Push(SeqStack *S, DataType2 x) {
    if (StackFull(S)) {
        printf("overflow");
        exit(0);
    } else {
        S->top = S->top + 1;
        S->data[S->top] = x; //将x入栈
    }
}

/*退栈*/
DataType2 Pop(SeqStack *S) {
    if (StackEmpty(S)) {
        printf("underflow");
        exit(0);
    }
    return S->data[S->top--];
}

/*取栈顶元素，不改变栈顶指针*/
DataType2 GetTop(SeqStack *S) {
    if (StackEmpty(S)) {
        printf("stack empty");
        exit(0); //出错退出处理。
    } else {
        return S->data[S->top]; //返回栈顶元素。
    }
}

/*利用栈的非递归中序遍历算法*/
void InOrder1(BinTree bt) {
    SeqStack S;
    BinTNode *p, *q;
    BinTNode *temp;
    InitStack(&S);
    Push(&S, bt);
    while (!StackEmpty(&S)) {
        while (GetTop(&S)) {
            Push(&S, GetTop(&S)->lchild); /*push后top会变*/
            // printf("data:%c", GetTop(&S)->data);
        }
        p = Pop(&S);
        if (!StackEmpty(&S)) {
            printf("%c", GetTop(&S)->data);
            p = Pop(&S);
            Push(&S, p->rchild); //右子树进栈
        }
    }
}

#define MAX_NODE 50
void InOrder2(BinTree T) {
    BinTNode *Stack[MAX_NODE], *p = T;

    int top = 0, bool = 1;

    if (T == NULL)
        printf("Binary Tree is Empty!\\n");
    else {
        do {
            while (p != NULL) {
                Stack[++top] = p;
                p = p->lchild;
            }

            if (top == 0)
                bool = 0;
            else {
                p = Stack[top];
                top--;
                printf("%c", p->data);
//                visit(p->data);
                p = p->rchild;
            }

        } while (bool != 0);
    }
}

void LevelorderTraverse(BinTNode *T) {
    BinTNode *Queue[MAX_NODE], *p = T;
    int front = -1, rear = -1;
    if (p != NULL) {
        Queue[++rear] = p; /* 根结点入队 */

        while (front < rear) {
            p = Queue[++front];
//            visit(p->data);
            printf("%c", p->data);
            if (p->lchild != NULL)
                Queue[++rear] = p->lchild; /* 左结点入队 */
            if (p->rchild != NULL)
                Queue[++rear] = p->rchild; /* 左结点入队 */
        }
    }
}

void test01() {
//    char str[] = "(A(B(,D(E,F)),C))";
//    char str[] = "(A(B(,D),C(E,F)))";
    char str[] = "(a(b(c,d(e(,g),f))))";

    //   printf("%c", str[0]);
    BinTNode *btree = CreateTree(str);
    //printf("%c", btree->data);
    //preOrder(btree);
    //InOrder(btree);
    //postOrder(btree);
    LevelorderTraverse(btree);

    //char str[] = "(A(B(,D(E,F)),C))";
    //  printf("%c", str[0]);
    // BinTNode *btree = CreateTree(str);
    //printf("%c", btree->data);
}

void test02() {

    char str[] = "(A(B,C)";
    BinTNode *btree = CreateTree(str);
    printBtree2(btree);
}

/*以二叉链表为存储结构，试编写在二叉树中查找值为E的结点以及结点在树中层数的算法*/
int found = 0;

int FindBt(BinTree bt, DataType x, int level) {
    if (bt != NULL && found == 0) {
        printf("CurrentData:%c,index:%d", bt->data, level);

        if (bt->data == x) {
            printf("End%d", level);
            found = 1;
            return level;
        } else {
            FindBt(bt->lchild, x, level + 1); //左子树
            FindBt(bt->rchild, x, level + 1); //右子树
        }
    }
    return level;
}
/**
                   *
                *      *
              *   *   *  *
 */
void test03() {
    char str[] = "(A(B(,D(E,F)),C))";
    BinTNode *btree = CreateTree(str);
    int level = 0;
    level = FindBt(btree, 'D', level);
}

///*线索化*/
//typedef struct tri2node {
//    DataType data;
//    int ltag, rtag;
//    struct tri2node *lchild, *rchild;
//} BinTri2Node;
//typedef BinTri2Node *BinTri2Tree;
//
//void InorderThread(BinTri2Tree bt) {
//    static BinTri2Node *pre = NULL;
//    if (bt != NULL) {
//        InorderThread(bt->lchild); //左子树线索化
//        if (bt->lchild == NULL)
//            bt->ltag = 1;
//        else
//            bt->ltag = 0;
//        if (bt->rchild = NULL)
//            bt->rtag = 1;
//        else
//            bt->rtag = 0;
//        if (pre) {
//            if (pre->rtag == 1)
//                pre->rchild = bt; //给前趋结点加后继线索
//            if (bt->ltag == 1)
//                bt->lchild = pre; //给当前结点加前趋线索
//        }
//        pre = bt;                  //将刚访问过的当前结点置为前趋结点。
//        InorderThread(bt->rchild); //右子树线索化
//    }
//}
//
/*查找某结点*p的后继结点*/
//BinTri2Node *InorderNext(BinTri2Node *p) {
//    if (p->rchild->rtag == 1) {
//        return p->rchild;
//    } else {
//        p = p->rchild;
//        while (p->ltag == 0) //沿左指针向下查找
//        {
//            p = p->lchild;
//        }
//        return p;
//    }
//}
int main() {
    test01();
//    system("pause");
    return 0;
}